import java.util.Random;
import java.util.Scanner;

public class main {
    static char[][] chess = new char[4][4];
    static char player;
    static char computer;
    static Scanner input=new Scanner(System.in);

    public static void main(String[] args){


        StartGame();

        String current = "player";
        while (!main.Win(main.computer) && !main.Win(main.player) && !main.isEmpty()) {
            //当有一方获胜或者棋盘是空的时候终止。
            switch (current) {
                case "player":
                    main.playerGo();
                    current = "computer";
                    break;//当玩家下完后轮到电脑下
                case "computer":
                    main.computerGo();
                    current = "player";
                    break;
                default:
                    break;
            }
        }

        //最终的结果界面 显示结果
        if (main.Win(main.computer)) {
            System.out.println("Computer win！");
        } else if (main.Win(main.player)) {
            System.out.println("player win!");
        } else {
            System.out.println("it ends in a draw！");
        }

    }

    //游戏开始界面
    public static void StartGame() {
        for (int i = 1; i < 4; i++)
            for (int j = 1; j < 4; j++)
                chess[i][j] = '-';
        //首先让用户选择使用的符号：1为符号X,2为符号O
        System.out.println("Welcome to tic tac toe man-machine interface");
        System.out.println("Please select your game symbol: X / O, enter the number 1 as X and the number 2 as O!");


        int a = input.nextInt();

        if (a == 1) {

            player = 'X';
            computer = 'O';

        } else if (a == 2) {

            player = 'O';
            computer = 'X';
        } else {

            player = 'X';
            computer = 'O';

            System.out.println("Input error, the player defaults to the symbol X");

        }

        //玩家选择先手还是后手 先手为1后手为2
        System.out.println("Enter 1 to select the first hand, and enter 2 to select the second hand");

        int hand= input.nextInt();
        if (hand == 1) {
            //玩家选择先手则先将棋盘绘制出
            Print();

        } else if (hand == 2) {
            //玩家后手则电脑下棋
            Random rand = new Random();
            int row = rand.nextInt(3) + 1;
            int col = rand.nextInt(3) + 1;
            chess[row][col] = computer;
            //电脑下完棋之后绘制棋盘
            Print();
        } else {
            //输入了错误的字符，默认玩家先手，绘制棋盘
            System.out.println("Input wrong characters, default player first!");
            Print();
        }

    }

    //绘制棋盘
    static void Print() {
        System.out.println("**********");
        for (int i = 1; i < 4; i++) {
            for (int j = 1; j < 4; j++) {
                System.out.print("| ");
                System.out.print(chess[i][j] + " ");
                if (j == 3) System.out.println("|");
            }
            if (i == 3) System.out.println("**********");
        }

    }


    //判断输赢 共有八种可能
    public static Boolean Win(char player) {
        //水平直线 竖直直线
        if (chess[1][1] == player && chess[1][2] == player && chess[1][3] == player) {
            return true;
        }
        if (chess[2][1] == player && chess[2][2] == player && chess[2][3] == player) {
            return true;
        }
        if (chess[3][1] == player && chess[3][2] == player && chess[3][3] == player) {
            return true;
        }
        if (chess[1][1] == player && chess[2][1] == player && chess[3][1] == player) {
            return true;
        }
        if (chess[1][2] == player && chess[2][2] == player && chess[3][2] == player) {
            return true;
        }
        if (chess[1][3] == player && chess[2][3] == player && chess[3][3] == player) {
            return true;
        }
        //斜线
        if (chess[1][1] == player && chess[2][2] == player && chess[3][3] == player) {
            return true;
        }
        return chess[1][3] == player && chess[2][2] == player && chess[3][1] == player;
    }


    //判断棋盘是否还有地方能下棋子
    public static boolean isEmpty() {
        //判断棋盘是否为空
        for (int i = 1; i < 4; i++) {
            for (int j = 1; j < 4; j++) {
                if (chess[i][j] == '-')
                    return false;
            }
        }
        return true;
    }

    //玩家开始下棋
    public static void playerGo() {

        System.out.println("--------------------------：                                    1，2，3");
        System.out.println("It's your turn to go. Please enter the chess piece position:    4，5，6");
        System.out.println("--------------------------：                                    7，8，9");

        int row, col;
        int a = input.nextInt();

        if (a >= 1 && a <= 9) {

            if (a % 3 == 0) row = a / 3;
            else row = a / 3 + 1;
            col = a - 3 * (row - 1);
            if (chess[row][col] != '-') {
                //判断玩家选择的位置是否有已经有棋子
                System.out.println("There are already pieces in this position");
                playerGo();
            }

            chess[row][col] = player;
            Print();

        } else {
            //输入错误给予提示
            System.out.println("Your character input is wrong, please re-enter!");
            playerGo();

        }

    }

    //电脑开始下棋
    public static void computerGo() {

        int best = 0;
        int bestScore = -1000;
        int score;
        for (int i = 1; i <= 3; i++) {
            for (int j = 1; j <= 3; j++) {
                if (chess[i][j] == '-') {
                    chess[i][j] = computer;
                    score = bestInput("player", "computer", -10000, 10000);//剪枝算法
                    if (score >=bestScore) {
                        //在同一层的节点里面需要不断试探性递归，用回溯法找到最合适的下棋点使自己胜算最大
                        bestScore = score;
                        best = (i - 1) * 3 + j;
                    }
                    chess[i][j] = '-';
                }
            }
        }
        int row, col;
        if (best % 3 == 0)
            row = best / 3;
        else
            row = best / 3 + 1;
        col = best - (row - 1) * 3;
        chess[row][col] = computer;
        Print();


    }

    //剪枝算法（-1玩家赢，1电脑赢，0平局）
    /*
    alpha剪枝思路：
   1.检查当前局面是否已分胜负。如果已分，返回结果，否则进入步骤2。
   2.如果本层是max层，搜索下一层可能的局面，根据可能的值更新本层的alpha，并且返回本层的beta给上层。否则更新本层的beta,并且把本层的alpha返回上一层
     */
    static int bestInput(String state, String nextState, int alpha, int beta) {
        //输入，调用剪枝的过程
        char ch;
        if (state.equals("computer")) {
            ch = computer;
        } else {
            ch = player;
        }

        if (Win(ch)) {
            if (state.equals("computer")) {
                //电脑赢
                return 1;
            } else {
                //玩家赢
                return -1;
            }
        } else if (isEmpty()) {
            //平局
            return 0;
        } else {
            int score;
            for (int i = 1; i < 4; i++) {
                for (int j = 1; j < 4; j++) {
                    if (chess[i][j] == '-') {
                        chess[i][j] = ch;
                        score = bestInput(nextState, state, alpha, beta);
                        chess[i][j] = '-';
                        if (state.equals("computer")) {
                            //max层
                            if (score >= alpha) {
                                alpha = score;
                            }
                            if (alpha > beta) {
                                return beta;
                            }
                        } else {
                            //min层
                            if (score < beta) {
                                beta = score;
                            }
                            if (beta <= alpha) {
                                return alpha;
                            }
                        }
                    }
                }
            }
            if (state.equals("computer")) {
                return alpha;
            } else {
                return beta;
            }
        }
    }


}
